% This is "sig-alternate.tex" V1.9 April 2009
% This file should be compiled with V2.4 of "sig-alternate.cls" April 2009
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.4 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.4) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@hq.acm.org)
% ===============================================================
%
% For tracking purposes - this is V1.9 - April 2009

\documentclass{sig-alternate}

\usepackage{url}
\usepackage{algorithm}
\usepackage{algorithmic}
%
\usepackage{subfigure}
\usepackage{epsfig,amsmath,color, amsfonts}
\usepackage{epsfig,color}
%\usepackage{framed}
%%\usepackage{epsf}
\usepackage{psfrag}
%\usepackage{hyperref}
%\usepackage{pdfpages}
%%\usepackage{fullpage}
%\usepackage{color}
%
\usepackage[latin1]{inputenc}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\usepackage{theorem}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
%\theoremstyle{definition}\newtheorem{example}[theorem]{Example}
\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
%\newtheorem{definition}[theorem]{Definition}
\theoremstyle{observation}\newtheorem{observation}[theorem]{Observation}
%\newtheorem{observation}[theorem]{Observation}
\theoremstyle{definition}\newtheorem{example}[theorem]{Example}

\newcommand{\comment}[1]{}
\newcommand{\QED}{\mbox{}\hfill \rule{3pt}{8pt}\vspace{10pt}\par}
%\newcommand{\eqref}[1]{(\ref{#1})}
\newcommand{\theoremref}[1]{(\ref{#1})}
\newenvironment{proof1}{\noindent \mbox{}{\bf Proof:}}{\QED}
%\newenvironment{observation}{\mbox{}\\[-10pt]{\sc Observation.} }%
%{\mbox{}\\[5pt]}

\def\figspace{0}
\def\m{{\rm min}}
%\def\m{\bar{m}}
\def\eps{{\epsilon}}
\def\half{{1\over 2}}
\def\third{{1\over 3}}
\def\quarter{{1\over 4}}
\def\polylog{\operatorname{polylog}}


%---------------------
%  SPACE SAVERS
%---------------------
%\usepackage{times}
%\usepackage[small,compact]{titlesec}
%\usepackage[small,it]{caption}
%%\smallskip

%\newcommand{\squishlist}{
% \begin{list}{$\bullet$}
%  { \setlength{\itemsep}{0pt}
%     \setlength{\parsep}{3pt}
%     \setlength{\topsep}{3pt}
%     \setlength{\partopsep}{0pt}
%     \setlength{\leftmargin}{1.5em}
%     \setlength{\labelwidth}{1em}
%     \setlength{\labelsep}{0.5em} } }
%\newcommand{\squishend}{
%  \end{list}  }


\newcommand{\squishlist}{\begin{itemize}}
\newcommand{\squishend}{\end{itemize}}


%---------------------------------
% FOR MOVING PROOFS TO APPENDIX
%\usepackage{answers}
%%\usepackage[nosolutionfiles]{answers}
%\Newassociation{movedProof}{MovedProof}{movedProofs}
%\renewenvironment{MovedProof}[1]{\begin{proof}}{\end{proof}}

\def\e{{\rm E}}
\def\var{{\rm Var}}
\def\ent{{\rm Ent}}
\def\eps{{\epsilon}}
\def\lam{{\lambda}}
\def\bone{{\bf 1}}


\def\EQ{\mbox{\tt EQ}}
\def\EQfunc{\mbox{\tt eq}}
\def\DISJ{\mbox{\tt DISJ}}
\def\DISJfunc{\mbox{\tt disj}}
\def\LAB{\mbox{\tt MAX\_Label}}

\def\cP{\mathcal{P}}
\def\cH{\mathcal{H}}
\def\cA{\mathcal{A}}
\def\cT{\mathcal{T}}
\def\cD{\mathcal{D}}
\def\cC{\mathcal{C}}
\def\cG{\mathcal{G}}
\def\cJ{\mathcal{J}}
\def\cF{\mathcal{F}}
\def\hC{\hat{\mathcal{C}}}
\def\tO{{\tilde{O}}}
\def\INPUT{\bar{x}^s,\bar{x}^r}
\def\INPUTPrime{\bar{x'}^s,\bar{x'}^r}
\def\INPUTS{\bar{x}^s}
\def\INPUTR{\bar{x}^r}
\def\indVarS{X^s}
\def\indVarR{X^r}
\def\partyA{P_A}
\def\partyB{P_B}
\def\sminus{\smallsetminus}
\def\figspace{0}

\def\property{\mathcal{P}}



\newcommand{\diam}{\Lambda}
\newcommand{\numpaths}{\Gamma}
\newcommand{\pathlength}{L}
\newcommand{\graph}{G(\Gamma, \kappa, \Lambda)}
\newcommand{\algorithmsize}[0]{}
\def\PC{\mbox{\sc pc}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Appendix
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Comments
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\def\danupon#1{\marginpar{$\leftarrow$\fbox{D}}\footnote{$\Rightarrow$~{\sf #1 --Danupon}}}
%
%\def\stephan#1{\marginpar{$\leftarrow$\fbox{S}}\footnote{$\Rightarrow$~{\sf #1 --Stephan}}}
%
%\def\atish#1{\marginpar{$\leftarrow$\fbox{A}}\footnote{$\Rightarrow$~{\sf #1 --Atish}}}
%%
%Second definitions. Use these to remove all comments.


\def\danupon#1{}
\def\stephan#1{}
\def\atish#1{}

\def\note#1{}

\begin{document}
%
% --- Author Metadata here ---
\conferenceinfo{PODC'11,} {June 6--8, 2011, San Jose, California, USA.}
\CopyrightYear{2011}
\crdata{978-1-4503-0719-2/11/06}
\clubpenalty=10000
\widowpenalty = 10000
% --- End of Author Metadata ---


\renewcommand{\paragraph}[1]{\medskip\noindent{\bf #1}}
\renewenvironment{proof}[1][Proof]{\begin{trivlist} \item[\hskip \labelsep {\sc #1}.]}{\hfill\qed\end{trivlist}}

\title{A Tight Unconditional Lower Bound on Distributed Random Walk Computation
\titlenote{A full version of this paper is available as \cite{NanongkaiDP-Arxiv11} at
\url{http://arxiv.org/abs/1102.2906}}}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\newfont{\eaddfntsmall}{phvr8t at 11pt}

\numberofauthors{3} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%

% THIS IS A SHORT VERSIOM
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
\alignauthor Danupon Nanongkai\\
       %\affaddr{Faculty of Computer Science, The University of Vienna}\\
       \affaddr{University of Vienna \& Georgia Institute of Technology}\\
       \affaddr{Austria \& USA}
       \\ \email{danupon@gmail.com}
\alignauthor
Atish {Das Sarma}\\
       \affaddr{Google Research}\\
       \affaddr{Mountain View, USA.}
       \\ \email{dassarma@google.com}
\alignauthor Gopal Pandurangan\titlenote{Supported in part by the following grants: Nanyang Technological University grant  M58110000, NSF grant CCF-1023166, and by a grant from the United States-Israel Binational Science Foundation (BSF).}
\\
       \affaddr{Nanyang Technological University \& Brown University}\\
       \affaddr{Singapore \& USA}
       \\ \email{gopalpandurangan@gmail.com}
}



\maketitle

\begin{abstract}
We consider the problem of performing a random walk in a distributed network. Given bandwidth constraints, the goal of the problem is to minimize the number of rounds required to obtain a random walk sample. Das Sarma et al. [PODC'10] show that a random walk of length $\ell$ on a network of diameter $D$ can be performed in $\tilde O(\sqrt{\ell D}+D)$ time. A major question left open is whether there exists a faster algorithm, especially whether the multiplication of $\sqrt{\ell}$ and $\sqrt{D}$ is necessary.

In this paper, we show a tight unconditional lower bound on the time complexity of distributed random walk computation. Specifically, we show that for any $n$, $D$, and $D\leq \ell \leq (n/(D^3\log n))^{1/4}$, performing a random walk of length $\Theta(\ell)$ on an $n$-node network of diameter $D$ requires $\Omega(\sqrt{\ell D}+D)$ time. This bound is {\em unconditional}, i.e., it holds for any (possibly randomized) algorithm. To the best of our knowledge, this is the first lower bound that the diameter plays a role of multiplicative factor. Our bound shows that the algorithm of Das Sarma et al. is time optimal.

Our proof technique introduces a new connection between {\em bounded-round} communication complexity and distributed algorithm lower bounds with $D$ as a trade-off parameter, strengthening the previous study by Das Sarma et al. [STOC'11]. In particular, we make use of the bounded-round communication complexity of the pointer chasing problem. Our technique can be of independent interest and may be useful in showing non-trivial lower bounds on the complexity of other fundamental distributed computing problems.
\end{abstract}

%http://portal.acm.org/ccs.cfm?part=author&coll=portal&dl=GUIDE
% A category with the (minimum) three required fields

\category{C.2.4}{Computer Systems Organization}{Computer-Communication Networks}[Distributed Systems]
\category{F.0}{Theory of Computation}{General}
\category{G.2.2}{Mathematics of Computing}{Discrete Mathematic}[Graph Theory]
\terms{ Algorithms, Theory}

\keywords{Distributed Algorithms, Random Walk, Lower Bound, Time Complexity, Communication Complexity}



\input{introduction}
\input{simulation_theorem}
\input{pointer_chasing}
\input{main_theorem}
\input{conclusion}




%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\bibliographystyle{abbrv}
\bibliography{randomwalk-lowerbound}  % sigproc.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns


%\newpage
%\appendix
%\section*{Appendix}
%\input{omitted_proofs}

%
%
%\appendix
%%Appendix A
%\section{Headings in Appendices}
%The rules about hierarchical headings discussed above for
%the body of the article are different in the appendices.
%In the \textbf{appendix} environment, the command
%\textbf{section} is used to
%indicate the start of each Appendix, with alphabetic order
%designation (i.e. the first is A, the second B, etc.) and
%a title (if you include one).  So, if you need
%hierarchical structure
%\textit{within} an Appendix, start with \textbf{subsection} as the
%highest level. Here is an outline of the body of this
%document in Appendix-appropriate form:
%\subsection{Introduction}
%\subsection{The Body of the Paper}
%\subsubsection{Type Changes and  Special Characters}
%\subsubsection{Math Equations}
%\paragraph{Inline (In-text) Equations}
%\paragraph{Display Equations}
%\subsubsection{Citations}
%\subsubsection{Tables}
%\subsubsection{Figures}
%\subsubsection{Theorem-like Constructs}
%\subsubsection*{A Caveat for the \TeX\ Expert}
%\subsection{Conclusions}
%\subsection{Acknowledgments}
%\subsection{Additional Authors}
%This section is inserted by \LaTeX; you do not insert it.
%You just add the names and information in the
%\texttt{{\char'134}additionalauthors} command at the start
%of the document.
%\subsection{References}
%Generated by bibtex from your ~.bib file.  Run latex,
%then bibtex, then latex twice (to resolve references)
%to create the ~.bbl file.  Insert that ~.bbl file into
%the .tex source file and comment out
%the command \texttt{{\char'134}thebibliography}.
%% This next section command marks the start of
%% Appendix B, and does not continue the present hierarchy
%\section{More Help for the Hardy}
%The sig-alternate.cls file itself is chock-full of succinct
%and helpful comments.  If you consider yourself a moderately
%experienced to expert user of \LaTeX, you may find reading
%it useful but please remember not to change it.
%%\balancecolumns % GM June 2007
%% That's all folks!
\end{document}
